import java.util.*;


public class Partition {
    public static ListNode partition(ListNode pHead, int x) {
        // write code here
        if(pHead==null){
            return null;
        }
        ListNode head=new ListNode(-1);
        ListNode head1=head;
        ListNode cur=pHead;
        ListNode heado=new ListNode(-1);
        ListNode head2=heado;
        while (cur!=null){
            //小于的话添加新的链表中
            if(cur.val<x){
                //添加
                head1.next=cur;
                head1=head1.next;
            }else {
                //旧连表继续添加
                head2.next=cur;
                head2=head2.next;
            }
            cur=cur.next;
        }
        //在最后的尾结点必须要手动置空才行
        //if()
        if(head==null){
            return heado.next;
        }
        head1.next=heado.next;
        if(head2!=null){
            head2.next=null;
        }
        return head.next;
    }

    public static void main(String[] args) {
        ListNode listNode1=new ListNode(2);
        ListNode listNode2=new ListNode(4);
        ListNode listNode3=new ListNode(5);
        ListNode listNode4=new ListNode(6);
        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        System.out.println(partition(listNode1, 8));
    }
}